/**
 * 139. 单词拆分
 * https://leetcode-cn.com/problems/word-break/
 */

/**
 * @constructor
 * @return {{ val: boolean, children: TireNode[] }}
 */
function TireNode() {
  this.val = false;
  this.children = new Array(26).fill(null);
}

/**
 * @param {string[]} words
 * @constructor
 */
function Tire(words) {
  this.root = new TireNode();
  let curNode;
  for (let i = 0; i < words.length; i += 1) {
    curNode = this.root;
    const word = words[i];
    for (let j = 0; j < word.length; j += 1) {
      const index = word.charCodeAt(j) - Tire.codeA;
      if (!curNode.children[index]) {
        curNode.children[index] = new TireNode();
      }
      curNode = curNode.children[index];
    }
    curNode.val = true;
  }
}
Tire.codeA = 'a'.charCodeAt(0);
/**
 * @param {string} str
 * @param {number} begin
 * @param {number} end
 * @return {boolean}
 */
Tire.prototype.has = function (str, begin, end) {
  let curNode = this.root;
  for (let i = begin; i <= end; i += 1) {
    const index = str.charCodeAt(i) - Tire.codeA;
    curNode = curNode.children[index];
    if (!curNode) {
      return false;
    }
  }
  return curNode.val;
};

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
function wordBreak(s, wordDict) {
  const tire = new Tire(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 0; i < s.length; i += 1) {
    for (let j = 0; j <= i; j += 1) {
      if (dp[j] && tire.has(s, j, i)) {
        dp[i + 1] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak('leetcode', ['leet', 'code']) === true);
console.log(wordBreak('applepenapple', ['apple', 'pen']) === true);
console.log(wordBreak('catsandog', ['cats', 'dog', 'sand', 'and', 'cat']) === false);
